A graph is a type of data structure in which pairs of vertices (also referred to as nodes) are connected by edges. Typically, the nodes in a graph each represent an element in a set, while the edges represent relationships among the elements. Thus, graphs tend to be a useful way of representing a variety of types of information.
A directed graph is one in which the edges have a direction. A tree is a type of directed graph data structure having a root node, and a number of additional nodes that are each either an internal node or a leaf node. The root node and internal nodes each have one or more “child” nodes and each is referred to as the “parent” of its child nodes. Leaf nodes do not have any child nodes. Edges in a tree are conventionally directed from parent to child. In a tree, nodes have exactly one parent. A generalization of trees, known as a directed acyclic graph (DAG), allows a node to have multiple parents, but does not allow the edges to form cycle. Thus, trees and DAGs tend to be useful for representing hierarchical information.
A design problem may be represented as a data structure, such as a tree, in which variables are associated with nodes of the data structure and the edges represent relationships among the nodes. Searching through a space of possible solutions to a design problem involves traversing the data structure and manipulating the variables in an attempt to find a state of the variables that represents a successful solution. If a change to a variable does not result in a successful solution, backtracking can be employed in which the change is undone and a different change is attempted. Undoing a change may require reversing the manipulations for a number of variables which depended upon the changed variable and, thus, may require backtracking over portions of the data structure. Where the data structure is a tree, this may require backtracking over multiple levels of the tree.
During a search, it may be necessary to backtrack repeatedly over portions of the data structure. Further, when a solution is found, it may be desired to locate other, more-optimal solutions. As a result, it may be necessary to save prior states of the data structure for future reference. Further, saving and retrieving many versions of the data structure can be cumbersome, particularly where each state of the data structure represents a large quantity of data.
Therefore, what is needed are improved techniques for managing graph data structures and, more particularly, for storing and retrieving state information for a graph data structure. It is toward these ends that the present invention is directed.